package com.yc.algorithm.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * leetcode 100题
 * <href a="https://leetcode-cn.com/problem-list/2cktkvj/">leetcode100题</href>
 * @author samuelchen
 * @version 1.0
 * @date 2022-01-11
 */
public class Solution100 {

    /**
     * NO.10
     * <code>正则匹配</code>
     * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
     *
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * @author samuelchen
     * @date 2022/1/11
     * @param s
     * @param p
     * @throws
     * @return boolean
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    private boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

    /**
     * NO.11
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
     * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *
     * 说明：你不能倾斜容器.
     * eg:
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * @author samuelchen
     * @date 2022/1/11
     * @param height 
     * @throws 
     * @return int
     */
    public int maxArea(int[] height) {
        // 双指针解法。 定义左右两个指针 l和r
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            // 因为盛水取决于矮的那个桶，因此需要取 Math.min(height[l], height[r])
            int area = Math.min(height[l], height[r]) * (r - l);
            // 取出盛水最多的结果 ans
            ans = Math.max(ans, area);
            // 遍历条件就是 左右指针对应的木板谁短，谁的指针就往中间移动
            if (height[l] <= height[r]) {
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }

    /**
     * 两数只和
     * 给定一个整数数组 nums 和一个整数目标值 target，
     * 请你在该数组中找出 和为目标值 target 的那 两个 整数，
     * 并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     *
     * @author samuelchen
     * @date 2022/1/11
     * @param nums
     * @param target
     * @throws
     * @return int[]
     */
    public int[] twoSum(int[] nums, int target) {
        // 通过hash表
        int[] result = new int[2];
        if (nums == null || nums.length == 0) {
           return result;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int sub = target - nums[i];
            if (map.containsKey(sub)) {
                return new int[]{map.get(sub), i};
            }
            map.put(nums[i], i);
        }
        return result;
    }

    /**
     * NO.15
     * 三数之和
     * 给你一个包含 n 个整数的数组 nums，
     * 判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * @author samuelchen
     * @date 2022/1/11
     * @param nums 
     * @throws 
     * @return java.util.List<java.util.List<java.lang.Integer>>
     */
    public List<List<Integer>> threeSum(int[] nums) {

        return null;
    }


    /**
     * 17. 电话号码的字母组合
     * 输入：digits = "23"
     * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
     */
    List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        doCombinations(digits, 0, "");
        return res;

    }

    private void doCombinations(String digits, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }
        List<String> list = getMap().get(digits.charAt(index));
        for (int i = 0; i < list.size(); i++) {
            doCombinations(digits, index + 1,s + list.get(i));
        }
    }

    private Map<Character, List<String>> getMap(){
        return new HashMap<Character, List<String>>() {{
            put('2', new ArrayList<String>() {{
                add("a");
                add("b");
                add("c");
            }});
            put('3', new ArrayList<String>() {{
                add("d");
                add("e");
                add("f");
            }});
            put('4', new ArrayList<String>() {{
                add("g");
                add("h");
                add("i");
            }});
            put('5', new ArrayList<String>() {{
                add("j");
                add("k");
                add("l");
            }});
            put('6', new ArrayList<String>() {{
                add("m");
                add("n");
                add("o");
            }});
            put('7', new ArrayList<String>() {{
                add("p");
                add("q");
                add("r");
                add("s");
            }});
            put('8', new ArrayList<String>() {{
                add("t");
                add("u");
                add("v");
            }});
            put('9', new ArrayList<String>() {{
                add("w");
                add("x");
                add("y");
                add("z");
            }});
        }};
    }


    /**
     * 19. 删除链表的倒数第 N 个结点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode index1 = head, index2 = head;
        for (int i = 0; i < n; i++) {
            index2 = index2.next;
        }
        if (index2 == null) {
            return head.next;
        }
        while (index2 != null) {
            index2 = index2.next;
            index1 = index1.next;
        }
        index1.next = index1.next.next;

        return head;
    }

    /**
     * 2. 两数相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre.next;
        int num = 0;

        while (l1 != null || l2 != null || num != 0) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + num;
            num  = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = node;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        return pre.next;

    }

    public class ListNode {

        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

     
     /**
      * 49. 字母异位词分组
      */
     public List<List<String>> groupAnagrams1(String[] strs) {
         return new ArrayList<>(Arrays.stream(strs)
                 .collect(Collectors.groupingBy(str -> {
                     char[] array = str.toCharArray();
                     Arrays.sort(array);
                     return new String(array);
         })).values());
     }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        int i = 0;
        Set<String> strSet = new HashSet<>();
        while (i < strs.length) {
            if (strSet.contains(strs[i])) {
                continue;
            }
            List<String> list = new ArrayList<>();
            list.add(strs[i]);
            Set<Character> set = new HashSet<>();
            char[] chars = strs[i].toCharArray();
            for (char aChar : chars) {
                set.add(aChar);
            }

            for (int j = i+1; j < strs.length; j++) {
                char[] str = strs[j].toCharArray();
                if (list.contains(strs[j])) {
                    list.add(strs[j]);
                    continue ;
                }
                if (str.length == 0){
                    continue;
                }
                int k = 0;
                boolean flag = false;
                while (k < str.length) {
                    flag |= set.contains(str[k]);
                    k++;
                }
                if (flag) {
                    strSet.add(strs[j]);
                    list.add(strs[j]);
                }
            }
            i ++;
            res.add(list);
        }
        return res;




//        for (int i = 0; i < strs.length; i++) {
//            char[] chars = strs[i].toCharArray();
//            List<String> list = new ArrayList<>();
//            boolean flag = true;
//            int i = 0;
//            while (i < chars.length) {
//                flag &= set.contains(chars[i]);
//                if (flag) {
//                    list.add();
//                }
//
//            }
//
//            for (int j = 0; j < chars.length; j++) {
//                if () {
//
//                }
//            }
//        }

    }


}

